package com.bluebridgecup.DP;

import java.util.Scanner;

public class 数字三角形 {
    // 静态二维数组 a，用于存储数字三角形中的每一个数字。数组大小设为 105x105，可根据实际情况调整以适应不同规模的数字三角形
    static int[][] a = new int[105][105];
    // 静态二维数组 dp，用于动态规划计算。dp[i][j] 表示从数字三角形顶部出发，到达第 i 行第 j 列位置时所经过路径上数字之和的最大值
    static int[][] dp = new int[105][105];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 从标准输入读取数字三角形的行数 n，后续将按照这个行数构建和处理数字三角形
        int n = in.nextInt();

        // 通过双重循环将数字三角形中的每个数字依次读入数组 a 中
        // 外层循环控制行数，从第 1 行开始，直到第 n 行
        // 内层循环控制每行的列数，第 i 行有 i 个数字，所以列数从 1 到 i
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = in.nextInt();
            }
        }

        // 使用动态规划方法计算到达每个位置的最大路径和
        // 外层循环遍历数字三角形的每一行
        // 内层循环遍历当前行的每一列，注意列数是从 1 到 i，因为第 i 行只有 i 个元素
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // 状态转移方程：当前位置 (i, j) 的最大路径和等于其上方 (i - 1, j) 或左上方 (i - 1, j - 1) 位置的最大路径和中的较大值，再加上当前位置的数字 a[i][j]
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
            }
        }

        // 初始化变量 ans 用于存储最后一排中最大的路径和，初始值设为 0
        int ans = 0;
        // 遍历最后一排的每个位置，找出最大的路径和
        for (int i = 1; i <= n; i++) {
            ans = Math.max(dp[n][i], ans);
        }
        // 输出最终结果，即从数字三角形顶部到底部的最大路径和
        System.out.println(ans);
    }
}